The present invention generally relates to the field of communication networks, and in particular to link capacity sharing and link bandwidth allocation in such networks.
Many communication networks of today support so-called elastic traffic such as the xe2x80x9cbest effortxe2x80x9d services provided in Internet Protocol (IP) based networks or the Available Bit Rate (ABR) traffic in ATM networks. Elastic traffic is typically established for the transfer of a digital object, such as a data file, a Web page or a video clip for local playback, which can be transmitted at any rate up to the limit imposed by the link capacity. Web browsing on the Internet in particular is a good and representative example of elastic traffic. Here, the xe2x80x9celasticityxe2x80x9d of the traffic is apparent as the user-perceived throughput (normally given in transmitted bits or bytes per time unit) when downloading for example a web page fluctuates in time depending on the overall system load.
The services delivered by IP based networks and the Internet in particular are called xe2x80x9cbest effortxe2x80x9d, because the networks generally do not provide any guarantee of the quality of service (QoS) received by the applications. The IP network only makes a best effort to provide the requested service. For instance, if an application requests the network to deliver an IP packet from one end-point to another, the network normally can not say what the delay through the network will be for that packet. In fact, the network does not even guarantee tat the packet will be delivered at all.
Therefore, terminals connected to an IP network have to handle packet losses and excessive packet delay situations. Such situations occur when there are too many applications simultaneously using the network resources. These congestion situations have a non-zero probability in IP based networks, because IP networks do not exercise call admission control (CAC). In other words, IP networks do not restrict the number of simultaneously connected users, and consequently if there are too many users utilizing the network resources there will be congestion and packet losses.
However, with the advent of real-time traffic and QoS requirements in EP networks, there is a need for exercising call admission control (CAC) in order to restrict the number of connections simultaneously present in the network.
An important aspect of call or connection admission control is that new calls arriving to the network may be rejected service in order to protect in-progress calls. In general, CAC algorithms such as those commonly in use for rigid traffic in conventional ATM networks provide a basic means to control the number of users in the network, thereby ensuring that admitted users get the bandwidth necessary to provide the QoS contracted for. Consequently, a CAC algorithm represents a trade-off between the blocking probability for new calls and the provided throughput for in-progress calls. In other words, the more users that the CAC algorithm admits into the network (which reduces the blocking probability) the smaller the provided throughput per-user becomes, since a greater number of users will share the total bandwidth, and vice versa.
Recent research has indicated that it is meaningful to exercise call admission control even for elastic traffic, because CAC algorithms provide a means to prevent TCP sessions from excessive throughput degradations.
The issue of applying CAC for elastic connections, and thereby providing a minimum throughput for Transmission Control Protocol (TCP) connections in the Internet has been addressed by Massoulie and Roberts in references [1-3]. Here, bandwidth is allocated to different users according to some fairness criteria.
It has been recognized by Gibbens and Kelly in references [4-5] that there is an intimate relationship between throughput and blocking probabilities for elastic traffic, and that this trade-off is connected to the issue of charging.
It has also been shown by Feng et al. in reference [6] that providing a minimum rate guarantee for elastic services is useful, because in that case the performance of the TCP protocol can be optimized.
As the Internet evolves from a packet network supporting a single best effort service class towards an integrated infrastructure for several service classes, there is also a growing interest in devising bandwidth sharing strategies, which meet the diverse needs of peak-rate guaranteed services and elastic services.
Similarly, modern ATM networks need to support different service classes such as Constant Bit Rate (CBR) and Available Bit Rate (ABR) classes, and it is still an open question how to optimally share the link capacity among the different service classes.
In general, the issue of bandwidth sharing, in the context of dynamically arriving and departing traffic flows and especially when users have different throughput and blocking requirements, is known from the classical multi-rate circuit switched framework to be an extremely complex problem.
The present invention overcomes these and other drawbacks of the prior art arrangements.
It is a first object of to invention to devise a link capacity/bandwidth sharing strategy that meets the diverse needs of rigid and elastic services in a mixed rigid-elastic traffic environment.
In particular, it is desirable to treat the issues of bandwidth sharing and blocking probabilities for elastic traffic in a common framework. In this respect, it is a second object of the present invention to provide a link capacity sharing mechanism that considers the throughput-to-blocking trade-off for elastic traffic. Specifically, it would be beneficial to develop and utilize a link capacity sharing algorithm that optimizes the throughput-to-blocking trade-off.
It is a further object of the invention to provide an appropriate call-level model of a transmission link carrying elastic traffic and to apply the call-level model for dimensioning the link bandwidth sharing for throughput-blocking optimality.
These and other objects are met by the invention as defined by the accompanying patent claims.
The invention concerns an efficient strategy for sharing link bandwidth in a mixed rigid-elastic traffic environment, as well as a strategy for sharing bandwidth among elastic traffic flows.
Briefly, the idea according to the invention is to share link capacity in a network by dividing the link capacity into a first common part for elastic as well as rigid (non-elastic) traffic and a second part dedicated for elastic traffic based on received network traffic inputs. Subsequently, one or more admission control parameters for the elastic traffic are determined based on the division of link capacity as well as received network traffic inputs.
The division of link capacity generally serves to share the link capacity between rigid and elastic traffic, and in particular to reserve a part of the link capacity to elastic traffic. Preferably, a minimum required capacity of the common part relating to rigid traffic is determined given a maximum allowed blocking probability for the rigid traffic. In this way, a certain grade of service (GoS) on call level is guaranteed for the rigid traffic on the link.
The admission control parameter(s) determined for elastic traffic generally serves to restrict the number of elastic traffic flows simultaneously present on the link. In particular, by formulating a call-level model for elastic traffic and determining a maximum number of admissible elastic traffic flows based on call-level constraints for the elastic traffic related to throughput and/or blocking, the throughput-to-blocking trade-off is fully considered. In this respect, the invention is capable of optimally allocating link bandwidth among elastic connections in the sense that blocking probabilities are minimized under throughput constraints, or the other way around, in the sense that the throughput is maximized under blocking constraints. In his way, the invention provides maximum link bandwidth utilization, either in terms of minimum blocking under throughput constraints or maximum throughput under blocking constraints.
Accordingly, an efficient strategy for sharing bandwidth in a mixed rigid-elastic traffic environment is provided. In particular, the bandwidth sharing algorithm guarantees a maximum blocking for rigid traffic as well as a minimum throughput and/or a maximum blocking for elastic traffic.
An important technical advantage of the invention is its ability to meet the diverse needs of rigid traffic and elastic traffic.
Another advantage of the invention is the ability to provide predictable quality of service for both the user and the network provider while at the same time ensuring high network provider revenue.
By considering only the elastic traffic of the overall traffic in a mixed rigid-elastic traffic environment, or alternatively by reducing the common bandwidth part to zero so that the entire link is reserved for elastic traffic, the overall link capacity sharing mechanism is reduced to We determination of one or more admission control parameters for elastic traffic. Admission control for requested new elastic connections can then be exercised based on such admission control parameter(s). In particular, by minimizing the blocking probabilities with respect to the number of admissible elastic connections under given throughput constraints for the elastic traffic, excessive blocking probabilities are avoided, while ensuring a given user throughput.
Another aspect of the invention concerns the application of a call-level model of a link supporting elastic traffic, for dimensioning the link bandwidth sharing for throughput-blocking optimality in an admission-control enabled IP network. In particular, an elastic traffic flow is modeled as having a bandwidth that fluctuates between a minimum bandwidth and peak bandwidth during the holding time of the traffic flow. Furthermore, the elastic traffic is associated with at least one of a minimum accepted throughput and a maximum accepted blocking probability.
A further aspect of the invention concerns a computational method for determining a Maxkov chain steady state distribution that is particularly advantageous for large state spaces. The Markov chain describes the dynamics of a link carrying a number of traffic classes including non-adaptive elastic traffic, and the computational method provides a good initial approximation of the steady state distribution based on Markov chain product form calculations.
Other aspects or advantages of the present invention will be appreciated upon reading of the below description of the embodiments of the invention.